package com.ting.test.algorithms.链表;

import java.util.HashMap;
import java.util.Stack;

/**
 * 给定一个单链表的头节点head，请判断该链表是否为回文结构。
 * <p>
 * 1）哈希表方法特别简单（笔试用）
 * <p>
 * 2）改原链表的方法就需要注意边界了（面试用）
 * 思路
 * 考虑用hashMap，把链表的每一个元素都放到hashMap中，然后按个比对
 * 如果完全一样，则表明，该链表元素是回文。
 */
public class 回文链表解法2 {
    public static void main(String[] args) {
        SingleNode head = new SingleNode();
        Boolean result = ishuiwen(head);
        System.out.println(result);
    }

    private static Boolean ishuiwen(SingleNode head) {
        HashMap<Integer, SingleNode> map = new HashMap();
        SingleNode node = head;
        int index = 1;
        do {
            map.put(index, node);
            index++;
        } while (node.next != null);

        // 倒序比较
        for (int i = index; i > 0; i--) {
            if (head.getValue() != map.get(i).getValue()) {
                return false;
            }
        }

        return true;
    }
}
